package com.leecode;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 139. 单词拆分
 * <p>
 * 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
 * 拆分时可以重复使用字典中的单词。
 * 你可以假设字典中没有重复的单词。
 * <p>
 * 示例 1：
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
 * <p>
 * 示例 2：
 * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
 * 输出: true
 * 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
 * 注意你可以重复使用字典中的单词。
 * <p>
 * 示例 3：
 * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出: false
 */
public class Leet139 {
	public static void main(String[] args) {
//		new Leet139().wordBreak("catsandog", Arrays.asList("cats", "dog", "sand", "and", "cat"));
		new Leet139().wordBreak("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", Arrays.asList("a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"));
//		new Leet139().wordBreak("leetcode", Arrays.asList("leet", "code"));
	}

	/**
	 * dfs+记忆
	 * dfs思路像"冒泡,穷举"
	 * 切a
	 *  切a
	 *  切aa
	 *  ...
	 * 切aa
	 *  切a
	 *  切aa
	 *  ...
	 *
	 */
	public boolean wordBreak(String s, List<String> wordDict) {
		if (s == null || wordDict == null) return false;

		return true;
	}
	/**
	 * 改良后的思路是对的,但会超时,如aaaaaaaaaaaaaaaaab [a,aa,b]
	 * 89%,93%
	 * 根据答案,学习了记忆优化
	 * aab [aa,a]
	 * 切aa,结果false,memory[2]==false
	 * 切a,再切a,memory[1+1]==false,引出recur要传递midx
	 */
	Boolean[] memory;
	public boolean wordBreak2(String s, List<String> wordDict) {
		if (s == null || wordDict == null) return false;
		memory=new Boolean[s.length()+1];
		Arrays.fill(memory,true);

		return dfs(s,wordDict,0);
	}
	public boolean dfs(String s, List<String> wordDict,int midx){
		if("".equals(s))return true;
		Collections.sort(wordDict);
		StringBuilder sb = new StringBuilder(s);
		h:
		for (int i = wordDict.size()-1; i >=0; i--) {
			String curWord = wordDict.get(i);
			int idx = sb.indexOf(curWord);//简单匹配逻辑,有bug,cats和cat,sand和and
			if(idx==0){
				if(memory[midx+curWord.length()].equals(false))return false;
				if(dfs(sb.delete(0, curWord.length()).toString(),wordDict,midx+curWord.length()))return true;
				else {
					sb.insert(0,curWord);//
					memory[midx+curWord.length()]=false;//记忆优化,关键步骤
				}
			}
		}
		return false;
	}
}
